package _binary_tree

import common.v1.Node
import org.junit.Assert
import org.junit.Test
import java.util.*
import kotlin.collections.ArrayList

/*
 https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/
 https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_429-n%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86

 429. N 叉树的层序遍历
 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
 */
class leetcode_429 {
    @Test
    fun test_1() {
        val root = Node(1)
        val n2 = Node(2)
        val n3 = Node(3)
        val n4 = Node(4)
        val n5 = Node(5)
        val n6 = Node(6)
        root.children = arrayListOf(n3, n2, n4)
        n3.children = arrayListOf(n5, n6)
        val actual = levelOrder(root)
        val expect: ArrayList<ArrayList<Int>> = arrayListOf(arrayListOf(1), arrayListOf(3, 2, 4), arrayListOf(5, 6))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val root = Node(1)
        val n2 = Node(2)
        val n3 = Node(3)
        val n4 = Node(4)
        val n5 = Node(5)
        val n6 = Node(6)
        val n7 = Node(7)
        val n8 = Node(8)
        val n9 = Node(9)
        val n10 = Node(10)
        val n11 = Node(11)
        val n12 = Node(12)
        val n13 = Node(13)
        val n14 = Node(14)
        root.children = arrayListOf(n2, n3, n4, n5)
        n3.children = arrayListOf(n6, n7)
        n4.children = arrayListOf(n8)
        n5.children = arrayListOf(n9, n10)
        n7.children = arrayListOf(n11)
        n8.children = arrayListOf(n12)
        n9.children = arrayListOf(n13)
        n11.children = arrayListOf(n14)

        val actual = levelOrder(root)
        val expect: ArrayList<ArrayList<Int>> = arrayListOf(
            arrayListOf(1), arrayListOf(2, 3, 4, 5), arrayListOf(6, 7, 8, 9, 10), arrayListOf(11, 12, 13), arrayListOf(14)
        )
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    private fun levelOrder(root: Node?): List<List<Int>> {
        // T - N
        // S - N
        val result: ArrayList<ArrayList<Int>> = ArrayList<ArrayList<Int>>()
        if (null == root) {
            return result
        }
        val queue: LinkedList<Node> = LinkedList<Node>()
        queue.offer(root)
        while (!queue.isEmpty()) {
            var size: Int = queue.size
            val list: ArrayList<Int> = ArrayList<Int>()
            while (size-- > 0) {
                val node = queue.poll()
                list.add(node.`val`)
                val children: List<Node?> = node.children
                for (node in children) {
                    node?.let { queue.offer(node) }
                }
            }
            result.add(list)
        }
        return result
    }

}